#include <iostream>
#include <vector>
#include <stack>
#include "DirectedWeightGraph.h"
using namespace std;

// 定义最大路径权值。若顶点间路径权值过大，认为两个顶点没有边连接。
const int MAX = 1000000;

// 求多段图的最短路径
void solve(const DirectedWeightGraph& dwg) {
    int n = dwg.V; // 图的顶点总数

    vector<int> cost(n, MAX); // cost数组记录最短路径长度
    vector<int> path(n, -1);  // path数组记录最短路径的上一节点位置

    // 初始化cost数组与path数组
    cost[0] = 0; // 初始化源点状态

    // 从j=1开始，考察从源点0到顶点j的所有入边
    for (int j = 1; j < n; j++) {
        int min = MAX;
        for (int i = 0; i < j; i++) {
            // 没有边连接, 跳过
            if (dwg.edges[i][j] >= MAX) continue;

            // 有边连接，更新cost[j]、path[j]
            if (cost[i] + dwg.edges[i][j] < min) {
                cost[j] = cost[i] + dwg.edges[i][j];
                min = cost[j];
                path[j] = i;
            }
        }
    }

    // 使用栈还原path并输出
    stack<int> pathStk;
    int i = n - 1;
    while (i != 0) {
        pathStk.push(i);
        i = path[i];
    }
    cout << "最短路径: 0"; // 源点
    while (!pathStk.empty()) {
        cout << " -> " << pathStk.top();
        pathStk.pop();
    }
    cout << endl;

    // 输出最短路径长度
    cout << "最短路径长度: " << cost[n - 1] << endl;
}

// 测试运行：创建有向加权图并计算最短路径
void test() {
    int n = 10; // 顶点个数为10

    // 创建顶点个数为10的有向加权图
    DirectedWeightGraph dwg(n);

    // 图初始化：输入所有的路径
    dwg.addEdge(0, 1, 4);
    dwg.addEdge(0, 2, 2);
    dwg.addEdge(0, 3, 3);
    dwg.addEdge(1, 4, 9);
    dwg.addEdge(1, 5, 8);
    dwg.addEdge(2, 4, 6);
    dwg.addEdge(2, 5, 7);
    dwg.addEdge(2, 6, 8);
    dwg.addEdge(3, 5, 4);
    dwg.addEdge(3, 6, 7);
    dwg.addEdge(4, 7, 5);
    dwg.addEdge(4, 8, 6);
    dwg.addEdge(5, 7, 8);
    dwg.addEdge(5, 8, 6);
    dwg.addEdge(6, 7, 6);
    dwg.addEdge(6, 8, 5);
    dwg.addEdge(7, 9, 7);
    dwg.addEdge(8, 9, 3);

    // 调用核心方法求解最短路径
    solve(dwg);
}

int main() {
    test();
    return 0;
}